package com.markpim.algo;

public class QuickSort {

	public QuickSort(int[] input) {
		long timeSum = 0;
		for (int i = 0; i < Apl.ACCURACY; i++) {
			startTime = System.currentTimeMillis();
			assert Apl.isSorted(quickSortRecursive(input, 0, input.length - 1)) : "Tries to quicksort but failed!";
			endTime = System.currentTimeMillis();
			timeSum += (endTime - startTime);
		}
		avgTime = timeSum / Apl.ACCURACY;
		done(input.length);
	}

	protected long startTime = 0;
	protected long endTime = 0;
	protected long operations = 0;
	protected long avgTime = 0;

	public void done(int count) {
		System.out.println("Quicksorted " + count + " integers");
		System.out.println("Sorted in " + avgTime
				+ " milliseconds");
		System.out.println(operations + " operations.");
		System.out.println(" -------------- ");
		System.out.println();
	}

	private int[] quickSortRecursive(int[] numbers, int low, int high) {
		int i = low, j = high;
		int pivot = numbers[low + (high - low) / 2];

		while (i <= j) {
			operations++;
			while (numbers[i] < pivot) {
				operations++;
				i++;
			}
			while (numbers[j] > pivot) {
				operations++;
				j--;
			}
			if (i <= j) {
				Apl.swap(numbers, i, j);
				i++;
				j--;
			}
		}
		if (low < j) {
			quickSortRecursive(numbers, low, j);
		}
		if (i < high) {
			quickSortRecursive(numbers, i, high);
		}

		return numbers;
	}
}
